package com.ddshuai.easy;

/**
 * 描述 新通教育
 * 给定一个二叉树，计算整个树的坡度。
 * 一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
 * 整个树的坡度就是其所有节点的坡度之和。
 *
 *
 * 输入:
 *          1
 *        /   \
 *       2     3
 *      / \   / \
 *     3  4  6  7
 * 输出: 1
 * 解释:
 * 结点的坡度 2 : 0
 * 结点的坡度 3 : 0
 * 结点的坡度 1 : |2-3| = 1
 * 树的坡度 : 0 + 0 + 1 = 1
 *
 * 注意:
 *
 * 任何子树的结点的和不会超过32位整数的范围。
 * 坡度的值不会超过32位整数的范围。
 * @author ddshuai
 * @date 2018-12-17 10:10
 **/
public class FindTilt {
    private int tilt = 0;
     static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public int findTilt(TreeNode root) {
        tofindTilt(root);
        return tilt;
    }

    public int tofindTilt(TreeNode root) {
        int sumNode = 0;
        if (root != null)
        {
            int sumLeft = tofindTilt(root.left);
            int sumRight = tofindTilt(root.right);
            tilt += Math.abs(sumLeft-sumRight);
            sumNode = sumLeft+ sumRight + root.val;
        }
        return sumNode ;
    }

    public static void main(String[] args) {
        FindTilt findTilt = new FindTilt();
        TreeNode treeNode = new TreeNode(1);

        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(3);

        treeNode.left  = treeNode1;
        treeNode.right = treeNode2;

        System.out.println(findTilt.findTilt(treeNode));
    }
}
